package com.leetcode.leetcode2;

import java.util.HashMap;
import java.util.Map;

/**
 * 最小覆盖子串
 *
 * @author luhd
 * @date 2024-05-22
 */
public class Practice76 {
    /**
     * 示例 1：
     *
     * 输入：s = "ADOBECODEBANC", t = "ABC"
     * 输出："BANC"
     * 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
     * 示例 2：
     *
     * 输入：s = "a", t = "a"
     * 输出："a"
     * 解释：整个字符串 s 是最小覆盖子串。
     * 示例 3:
     *
     * 输入: s = "a", t = "aa"
     * 输出: ""
     * 解释: t 中两个字符 'a' 均应包含在 s 的子串中，
     * 因此没有符合条件的子字符串，返回空字符串。
     */
    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println(minWindow(s, t));
    }

    public static String minWindow(String s, String t) {
        if(t.length()>s.length()) {
            return "";
        }
        Map<Character,Integer> needMap = new HashMap<>();
        Map<Character,Integer> windowMap = new HashMap<>();
        for(char c : t.toCharArray()) {
            needMap.put(c, needMap.getOrDefault(c, 0) + 1);
        }
        int left = 0, right = 0;
        int valid = 0;
        int start = 0, minLen =Integer.MAX_VALUE;
        while(right < s.length()) {
            char c = s.charAt(right);
            right ++;
            if(needMap.containsKey(c)) {
                windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);
                if (windowMap.get(c).intValue() == needMap.get(c).intValue()) {
                    valid ++;
                }
            }
            while(valid == needMap.size()) {
                if(right - left < minLen) {
                    start = left;
                    minLen = right - left;
                }
                char d = s.charAt(left);
                left ++;
                if (needMap.containsKey(d)) {
                    if (windowMap.get(d).intValue() == needMap.get(d).intValue()) {
                        valid --;
                    }
                    windowMap.put(d, windowMap.get(d)-1);
                }
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
































    /**
     * 寻找字符串s中包含字符串t所有字符的最小子串
     *
     * @param s 输入的源字符串
     * @param t 目标字符串，包含所有必须出现在窗口中的字符
     * @return 返回最小子串；如果不存在，则返回空字符串
     */
    // public static String minWindow(String s, String t) {
    //     // 存储需要匹配的字符及其数量
    //     Map<Character, Integer> need = new HashMap<>();
    //     // 存储当前窗口内匹配的字符及其数量
    //     Map<Character, Integer> window = new HashMap<>();
    //
    //     // 初始化need map
    //     for (char c : t.toCharArray()) {
    //         need.put(c, need.getOrDefault(c, 0) + 1);
    //     }
    //
    //     // 左右指针，valid用于记录窗口内满足need条件的字符数量
    //     int left = 0, right = 0;
    //     int valid = 0;
    //     // 记录最小覆盖子串的起始索引及长度
    //     int start = 0, minLen = Integer.MAX_VALUE;
    //
    //     // 开始滑动窗口遍历字符串s
    //     while (right < s.length()) {
    //         // c是将移入窗口的字符
    //         char c = s.charAt(right);
    //         // 右移窗口
    //         right++;
    //         // 如果当前字符是需要匹配的字符，则更新window map
    //         if (need.containsKey(c)) {
    //             window.put(c, window.getOrDefault(c, 0) + 1);
    //             // 如果当前字符在窗口内的数量满足了需要的数量，则valid+1
    //             if (window.get(c).intValue() == need.get(c).intValue()) {
    //                 valid++;
    //             }
    //         }
    //
    //         // 当窗口内所有需要的字符都满足了need的条件
    //         while (valid == need.size()) {
    //             // 更新最小覆盖子串
    //             if (right - left < minLen) {
    //                 start = left;
    //                 minLen = right - left;
    //             }
    //             // d是将移出窗口的字符
    //             char d = s.charAt(left);
    //             // 左移窗口
    //             left++;
    //             // 如果移出的字符是需要匹配的字符，则更新window map
    //             if (need.containsKey(d)) {
    //                 // 如果窗口内该字符的数量正好满足need，则valid-1
    //                 if (window.get(d).intValue() == need.get(d).intValue()) {
    //                     valid--;
    //                 }
    //                 window.put(d, window.get(d) - 1);
    //             }
    //         }
    //     }
    //
    //     // 如果minLen未被更新，则说明没有找到覆盖子串，返回空字符串；否则，根据start和minLen截取子串
    //     return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    // }

}
